The present invention relates to video coding, and in particular, to decoding of video that has been encoded using data dependency information.
In video coding, one way to increase compression is to represent the information in one portion of the image as the differences from other nearby portions of the image. For example, an image frame may be divided into a multi-pixel grid in which each data block in the grid contains an N×M arrangement of pixels. More specifically, in the MPEG-2 (H.262), MPEG-4 and H.264/AVC video coding schemes, the image frame may be divided into a grid of 16×16 pixels; each 16×16 block is referred to as a “macroblock”. The data representing a particular macroblock is typically encoded using the information from adjacent macroblocks, as shown in FIG. 1.
FIG. 1 illustrates data dependency between macroblocks in the H.264/AVC case. For the macroblock 100, the four macroblocks 102, 104, 106 and 108 provide data dependency. The macroblock 102 is above and to the right; the macroblock 104 is above; the macroblock 106 is above and to the left; and the macroblock 108 is to the left. The data dependency from the macroblocks 102 and 106 relates to intra-prediction and motion vector prediction. The data dependency from the macroblocks 104 and 108 relates to intra-prediction, motion vector prediction, and deblocking filtering. The image may then be processed in raster order as shown in FIG. 2.
FIG. 2 illustrates processing macroblocks in raster order for an image frame 200. Raster order processing starts in the upper-left macroblock 202 and proceeds along the row toward the upper-right macroblock 204. From the macroblock 204, the processing proceeds to the leftmost macroblock 206 on the next row. The processing continues in a left-to-right, top-to-bottom manner until the final macroblock 208 is processed.
Note that by processing an image frame in raster order as shown in FIG. 2, the data dependencies required for processing the macroblock 100 (see FIG. 1) are obtained. Specifically, when processing the macroblock 100, the macroblock 108 will have been previously processed according to the left-to-right raster order processing, and the macroblocks 102, 104 and 106 will have been previously processed according to the top-to-bottom raster order processing. Further note that to process a particular row, the data from the entire previous row is required to be available for data dependency purposes.
The H.264 standard allows for macroblocks to be transmitted out of order (that is, in an order other than raster order) using techniques referred to as flexible macroblock ordering (FMO) and arbitrary slice ordering (ASO). (A slice refers to a group of macroblocks.) However, even when video is transmitted out of order, the video is re-ordered prior to decoding, and decoding takes place in raster order as described above.
In this manner, video data is decoded in a linear fashion. One way to increase the rate of processing linear data is to increase the speed of the processing hardware.